āļø TitanCode Arena Challenge
In the world of TitanCode Arena, N elite players compete on a global leaderboard, where each player has a combat power score. The leaderboard is dynamic: players constantly win battles, gain upgrades, or suffer defeats, causing their power scores to change.
As the system architect, you must build a real-time leaderboard engine that efficiently handles:
- Query: Find the maximum combat power among players in rank range [L, R]
- Update: Instantly update a player's power score on the leaderboard
š„ Input Format
- First line:
N(number of players) andQ(number of operations) - Second line:
Nspace-separated integers (initial combat power scores) - Next
Qlines: Operations in format:Q L R- Query maximum power in ranks [L, R]U i val- Update rank i to power val
š¤ Output Format
For each Query operation, output the maximum combat power in the specified range.
šÆ Sample Test Case 1
6 5 4 7 2 9 5 1 Q 1 4 U 3 6 Q 1 4 U 0 10 Q 0 2
9 7 10
- Query [1, 4]: max(7, 2, 9, 5) = 9
- Update rank 3 to 6: [4, 7, 2, 6, 5, 1]
- Query [1, 4]: max(7, 2, 6, 5) = 7
- Update rank 0 to 10: [10, 7, 2, 6, 5, 1]
- Query [0, 2]: max(10, 7, 2) = 10
šÆ Sample Test Case 2
7 6 5 1 9 3 6 8 2 Q 0 3 U 1 10 Q 0 3 Q 2 5 U 5 4 Q 2 5
9 10 9 9
š§ Segment Tree Algorithm
A Segment Tree is a binary tree data structure that efficiently handles range queries and point updates on arrays. It's perfect for the TitanCode Arena leaderboard where we need fast access to maximum values in any rank range.
š³ Tree Structure
Each node in the segment tree represents a range of the array:
- Leaf nodes: Represent single array elements
- Internal nodes: Store the maximum of their two children
- Root node: Contains maximum of entire array
For array [4, 7, 2, 9, 5, 1], the tree stores maximums for all possible ranges.
š§ Building the Tree
void build(vector& arr, int node, int start, int end) { if (start == end) { tree[node] = arr[start]; // Leaf node } else { int mid = (start + end) / 2; build(arr, 2*node, start, mid); // Left child build(arr, 2*node+1, mid+1, end); // Right child tree[node] = max(tree[2*node], tree[2*node+1]); } }
Key: Recursively build from bottom-up, storing maximum at each node.
š Update Operation
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val; // Update leaf
} else {
int mid = (start + end) / 2;
if (idx <= mid)
update(2*node, start, mid, idx, val);
else
update(2*node+1, mid+1, end, idx, val);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
}
Process: Navigate to leaf, update value, propagate changes upward.
š Query Operation
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return INT_MIN; // Out of range
if (l <= start && end <= r) return tree[node]; // Fully inside
int mid = (start + end) / 2;
int left = query(2*node, start, mid, l, r);
int right = query(2*node+1, mid+1, end, l, r);
return max(left, right);
}
Strategy: Split range into parts covered by tree nodes, combine results.
ā” Complexity Analysis
- Build: O(n) - visit each element once to construct tree
- Query: O(log n) - traverse tree height
- Update: O(log n) - update path from root to leaf
- Space: O(n) - approximately 4n nodes in tree array
š Comparison with Other Methods
| Method | Build | Query | Update | Best For |
|---|---|---|---|---|
| Segment Tree | O(n) | O(log n) | O(log n) | ā Dynamic data |
| Sparse Table | O(n log n) | O(1) | ā No updates | Static data |
| Naive Approach | O(1) | O(n) | O(1) | Small arrays |